def merge_sort(lst, L, R):
    """
    归并排序
    :param lst:
    :param L:
    :param R:
    :return:
    """
    if L == R:
        return
    mid = L + ((R - L) >> 1)
    merge_sort(lst, L, mid)
    merge_sort(lst, mid + 1, R)
    merge(lst, L, mid, R)


def merge(lst, L, mid, R):
    tmp_lst = []
    p, q = L, mid + 1
    while p <= mid and q <= R:
        if lst[p] <= lst[q]:
            tmp_lst.append(lst[p])
            p += 1
        else:
            tmp_lst.append(lst[q])
            q += 1
    while p <= mid:
        tmp_lst.append(lst[p])
        p += 1
    while q <= R:
        tmp_lst.append(lst[q])
        q += 1

    for i in range(len(tmp_lst)):
        lst[L + i] = tmp_lst[i]


if __name__ == "__main__":
    arr = [4, 2, 6, 1, 9, 5]
    merge_sort(arr, 0, len(arr)-1)
    print(arr)
